from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        a=["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        n=len(digits)
        if n==0:
            return []
        ans=[]
        path=['']*n  # 注意 path 长度一开始就是 n，不是空列表
        # 递归
        def dfs(i):
            if i==n:
                ans.append(''.join(path))
                return
            # 遍历a里面的字符串
            for c in a[int(digits[i])]:
                path[i]=c  # 直接覆盖，不需要回溯
                dfs(i+1)
        dfs(0)
        return ans